【题解】 [HNOI2009]双递增序列 线性DP luoguP4728 | Qiuly's blog!

【题解】 [HNOI2009]双递增序列 线性DP luoguP4728

Posted on | In | Comments:

其实这题很容易设出四维的 $\rm{DP}$ ，也就是用 $dp_{i,j,x,y}$ 表示第一个序列的终止位置为 $i$ 且长度为 $x$，第二个序列的终止位置为 $j$ 且长度为 $y$ 是否成立 ，然后也很容易想到降维，枚举当前序列长度 $len$ 的时候知道了 $x$ 就已经知道 $y$ 了—— $y$ 就是 $len-x$ 。也就是说现在的 $DP$ 是 $O(n^3)$ 的，还需要优化。

考虑设 $dp_{i,j}$ 表示第一个序列的最终位置为 $i-1$ 且长度为 $j$ 时第二个序列的最终位置的最小值。枚举当前数字 $i$ ，然后分两种情况进行转移——将 $a_i$ 放到第一个序列末尾 $\texttt{and}$ 将 $a_i$ 放到第二个序列末尾。

放到第一个序列末尾很好想：因为当前第一个序列的结尾处就是 $a_{i-1}$ ，比较一下大小直接转移就好了：

因为第二个序列的末尾没变，所有直接转移就好。

接下来考虑将第 $i$ 个数放到第二个序列末尾的情况，其实第一个序列和第二个序列没区别，当然除了名字上有一个字的差异，假设第 $i-1$ 个数是第二个序列末尾，当前第一个序列的长度为 $j-1$ ，那么第二个序列的长度因该就是 $(i-1)-(j-1)$ 了，因为我们假设了第 $i-1$ 个数是第二个序列末尾，那么 $dp_{i-1,i-j}$ 又可以被解释为第二个序列的末尾为 $i-1$ 个数且第二个序列的长度为 $i-j$ 的时候第一个序列的末尾的最小值 ，如果这个最小值小于 $a_i$ ，说明 $a_i$ 可以接到第一个序列前面，那么这个时候第二个序列的末尾为 $a_{i-1}$ ，显然又有转移：

开始的时候我们将 $dp$ 数组赋成极大值，然后最后判断一下 $dp_{n,n/2}$ 这个状态变小没有就好。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e3+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int a[N],f[N][N];
int solve() {
    int n;IN(n);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i) IN(a[i]);
    a[0]=f[0][0]=-1;
    for(int i=1;i<=n;++i) {
        f[i][0]=a[i];
        for(int j=1;j<=i&&j<=n/2;++j) {
            if(a[i]>a[i-1]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            if(a[i]>f[i-1][i-j]) f[i][j]=min(f[i][j],a[i-1]);
        }
    }return f[n][n/2]<0x3f3f3f3f;
}

int main() {
    int T;IN(T);
    while(T--) puts(solve()?"Yes!":"No!");
    return 0;
}

感觉这道题的确很绕……=。=